package com.example.demo.leetcode.zuocheng.gaopin;


/**
 * 为了降低时间复杂度
 *  如: abcde 从c开始交换成  deabc
 *   (1)方法:  abc逆序，de逆序， 整体逆序(可以证明 没必要..)
 *   复杂度是O(n)
 *
 *   (2)方法二:(针对交换代价大)
 *   如果是 abcde
 *    2.1 第一次交换  de c  ab  (de短，的交换后不动,剩下c)
 *    2.2 第二次交换 de a c b (c和ab交换 c短, 剩下b)
 *    2.3 第三次交换 de a b c (b,c交换 没有剩下的 结束)
 *   时间复杂度O(n)/2
 *
 */
public class Arr_一个数组从n开始交换 {

    /**
     *
     *  方法二
     *      交换长度为size,差异值为diff = Lpartsize - Rpartsize
     *    (1) 左边长度 > 右边长度 ,
     *       交换后  左边下标 + size , 左边换长度变成diff
     *
     *     (2)右边长度 > 左边长度， 交换长度为size
     *      交换后 右边下标 - size  右边交换长度变成 -diff
     *
     */
    public static void exchange(String [] arr , int n){

        int LIndex = 0 ;
        int RIndex = arr.length -1;
        int lPart = n;
        int rPart = arr.length - n;
        int size = Math.min(lPart,rPart);
        int diff =lPart - rPart;
        changeSize(arr,LIndex,RIndex,size);
        //diff == 0 只用交换一次
        while(diff != 0 ){
            if(lPart > rPart){
                LIndex = LIndex+size;
                lPart = diff;
            }else{
                RIndex = RIndex -size;
                rPart = - diff;
            }
            size = Math.min(lPart,rPart);
            diff =lPart - rPart;
            changeSize(arr,LIndex,RIndex,size);
        }

    }

    // 从L开始  从R开始 交换size个
    public static void changeSize(String [] arr, int L ,int R, int size){
        for(int i =0 ; i<size;i++){
            swap(arr,L+size-i-1,R-i);
        }
    }



    public static void swap(String [] arr, int a ,int b){
        String temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;

    }




    public static void main(String[] args) {
        String [] arr={"a","b","c","d","e"};
        exchange(arr,3);
        for(String s : arr){
            System.out.println(s);
        }
    }




}
